\documentclass[landscape]{slides}

\usepackage[utf8x]{inputenc}
\usepackage[L7x]{fontenc}
\usepackage[lithuanian]{babel}
\usepackage[left=3cm,top=2cm,right=3cm,bottom=3cm,nohead,foot=1.5cm]{geometry}
\usepackage{graphicx}
\usepackage{color}

\title{Masugo --- maksimalių dažnų pografių paieškos įrankis}
\author{Kliment Olechnovič}
\date{2011}

\begin{document}

\maketitle


\begin{slide}
\textcolor{blue}{\Large{Pažymėti grafai}}

Pažymėtas grafas gali būti apibrėžtas kaip ketvertas $G=(V, E, L, \delta)$ kur:
\begin{itemize}
  \item $V$ yra viršūnių aibė
  \item $E \subseteq V \times V$ yra briaunų aibė
  \item $L$ yra žymių aibė
  \item $\delta : (V \cup E) \rightarrow L$ yra funkcija, kuri priskiria žymes viršūnėms ir briaunoms
\end{itemize}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Pažymėti grafai}}

\centering
\includegraphics[scale=0.9]{../masugo_doc/img/labelled_graph_subgraph_isomorphism.png}
\end{slide}

\begin{slide}
\textcolor{blue}{\Large{Pažymėtų grafų izomorfizmas}}

Dviejų pažymėtų grafų $A$ ir $B$ {\em izomorfizmas} yra tokia bijekcija  $f : V_A \rightarrow V_B$, kad teisingi šie teiginiai:
\begin{itemize}
  \item $\forall v \in V_A$, $\delta_A(e)=\delta_B(f(v))$
  \item $\forall (v,u) \in E_A$, $(f(v),f(u)) \in E_B$ ir $\delta_A(v,u)=\delta_B(f(v),f(u))$
\end{itemize}
Pažymėtas grafas $A$ vadinamas pažymėto grafo $B$ {\em izomorfiniu pografiu}, jeigu egzistuoja izomorfizmas $f : V_A \rightarrow V_C$, kur $C$ yra pažymėto grafo $B$ pografis.
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Pažymėtų grafų izomorfizmas}}

\centering
\includegraphics[scale=1.0]{../masugo_doc/img/labelled_graph_subgraph_isomorphism.png}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Maksimalūs dažni pografiai}}

Tarkime, duota grafų aibė $\Omega$ ir skaičius $0 < \sigma \leq 1$, vadinamas
{\em palaikymo slenksčiu}.

Tada {\em dažnu pografiu} vadinamas bet koks grafas $A$, kurį palaiko ne mažiau $|\Omega|*\sigma$ grafų iš $\Omega$.

Pažymėkime grafų aibės $\Omega$ dažnų pografių aibę kaip $\Psi$.
Tada {\em maksimaliu dažnu pografiu} vadinamas bet koks grafas $A \in \Psi$, kurį palaiko tik vienas grafas iš $\Psi$ --- pats $A$.
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Bendra schema}}

Grafų aibėje ieškoma dažnų pomedžių, o paskui kiekvienam dažnam pomedžiui ieškoma maksimalių dažnų pografių,
priklausančių to pomedžio ekvivalentiškumo klasei.
\end{slide}

\begin{slide}
\textcolor{blue}{\Large{Medžio normalizavimas --- šaknies priskirimas}}

\centering
\includegraphics[scale=1.5]{../masugo_doc/img/root_selection.png}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Medžio normalizavimas --- sutvarkymas}}

\centering
\includegraphics[scale=1.5]{../masugo_doc/img/rooted_tree_ordering.png}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Medžio normalizavimas --- automorfizmai}}

\centering
\includegraphics[scale=1.5]{../masugo_doc/img/automorphisms.png}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Medžio kanoninė eilutė}}

\centering
\includegraphics[scale=1.5]{../masugo_doc/img/rooted_tree_ordering.png}

Depth-first: ``ABCF\$G\$\$DE\$\$\$BDE\$\$\$B\#''

Breadth-first: ``A\$B\$B\$B\$CD\$D\$FG\$E\$E\#''
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Dažnų pomedžių išskaičiavimas}}

\centering
\includegraphics[scale=1.5]{../masugo_doc/img/enumeration_tree.png}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Dažnų pomedžių išskaičiavimas}}

\centering
\includegraphics[scale=0.8]{../masugo_doc/img/support_counting.png}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Dažnų pomedžių išskaičiavimas --- automorfizmai}}

\centering
\includegraphics[scale=1.2]{../masugo_doc/img/automorphism_pruning.png}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Grafų ekvivalentiškumo klasės}}

\centering
\includegraphics[scale=1.5]{../masugo_doc/img/equivalence_classes.png}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Ekvivalentiškumo klasės narių išskaičiavimas}}

\centering
\includegraphics[scale=1.5]{../masugo_doc/img/equivalence_class_enumeration.png}
\end{slide}


\begin{slide}
\centering
\textcolor{blue}{\Large{Trumpai apie baltymų struktūras}}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{DNR}}

\centering
\includegraphics[scale=0.8]{img/dna.png}
\end{slide}

\begin{slide}
\textcolor{blue}{\Large{DNR turinys}}
\begin{verbatim}
ATCGTTTGCAGGTTAACCACATGATAAATATAGAACGTCTA
GTGGATAAAGAGGAAACTGGCCCCTTGACTAGCAGTAGGAA
CAATTACTAACAAATCAGAAGCATTAATGTTACTTTATGGC
AGAAGTTGTCCAACTTTTTGGTTTCAGTACTCCTTATACTC
TTAAAAATGATCTAGGACCCCCGGAGTGCTTTTGTTTATGT
AGCTTACCATATTAGAAATTTAAAACTAAGAATTTAAGGCT
GGGCGTGGTGGCTCACGCCTGTAATCCCAGCACTTTGGGAG
GCCGAGGTGGGCGGATCACTTGAGGCCAGAAGTTTGAGACC
\end{verbatim}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Baltymą koduojanti seka}}

\centering
\includegraphics[scale=0.6]{img/genetic_code.png}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Aminorūgštys}}

\centering
\includegraphics[scale=0.8]{img/amino_acids.png}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Aminorūgščių grandinė}}

\centering
\includegraphics[scale=0.9]{img/peptide_bond_3D.png}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Folding}}

\centering
\includegraphics[scale=1.2]{img/folding.jpg}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Baltymo struktūra}}

\centering
\includegraphics[scale=0.8]{img/1ema.png}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Delone trianguliacija ir Voronoi diagrama}}

\includegraphics[scale=0.9]{img/Delaunay_circumcircles_centers.png}
\includegraphics[scale=0.9]{img/Delaunay_Voronoi.png}
\end{slide}

\begin{slide}
\textcolor{blue}{\Large{Baltymo atomų Delone trianguliacija}}

\centering
\includegraphics[scale=0.55]{img/voroprot_delaunay.png}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Baltymo atomų Voronoi diagrama}}

\centering
\includegraphics[scale=0.55]{img/voroprot_all_cells.png}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Baltymo atomų Voronoi diagramos dalis}}

\centering
\includegraphics[scale=0.55]{img/voroprot_residues_voronoi.png}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Baltymo atomų Voronoi diagramos dalis}}

\centering
\includegraphics[scale=0.55]{img/voroprot_voronoi.png}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Masugo pritaikymas baltymų struktūrų analizėje}}

\centering
\includegraphics[scale=0.8]{../masugo_doc/img/cullpdb_pc20_res18_log_plot_st_fst.png}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Masugo pritaikymas baltymų struktūrų analizėje}}

\centering
\includegraphics[scale=0.8]{../masugo_doc/img/cullpdb_pc20_res18_log_plot_st_mfsg.png}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Masugo pritaikymas cheminiams junginiams}}

\centering
\includegraphics[scale=0.6]{../masugo_doc/img/compound_log_plot_st_fst.png}
\includegraphics[scale=0.6]{../masugo_doc/img/compound_log_plot_st_mfsg.png}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Masugo pritaikymas baltymų struktūrų analizėje}}

\centering
\includegraphics[scale=0.5]{../masugo_doc/img/cullpdb_pc20_res18_subgraph_1.png}
\includegraphics[scale=0.5]{../masugo_doc/img/cullpdb_pc20_res18_subgraph_2.png}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Masugo pritaikymas baltymų struktūrų analizėje}}

\centering
\includegraphics[scale=0.5]{../masugo_doc/img/pdexk_subgraph_1.png}
\includegraphics[scale=0.5]{../masugo_doc/img/pdexk_subgraph_2.png}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Aminorūgščių hidrofobiškumas}}

\centering
\includegraphics[scale=1.0]{img/amino_acids_hydrophobicity.png}
\end{slide}


\begin{slide}
\textcolor{blue}{\Large{Aminorūgščių dažnumas rastuose pografiuose}}

Palaikymo slenkstis 0.5. Viso rasti 2807 pografiai.

LEU --- 6560, VAL --- 3123, ILE --- 3082, PHE --- 1290, ALA --- 578, PRO --- 22, TRP --- 10, MET --- 6

TYR --- 176, THR --- 74, ARG --- 41, GLU --- 35, SER --- 25, LYS --- 22, ASP --- 21, GLN --- 16, ASN --- 16, HIS --- 10, CYS --- 2

\end{slide}


\begin{slide}
\centering
\textcolor{blue}{\Large{Ačiū}}
\end{slide}


\end{document}